package sysu.el.graph.undi.algor;

import sysu.el.array.BoolArray;
import sysu.el.array.algors.Sig;
import sysu.el.array.ints.ArrInt;
import sysu.el.array.ints.ArrQueueInt;
import sysu.el.audit.Max2Int;
import sysu.el.audit.Max2IntDes;
import sysu.el.audit.MaxInt;
import sysu.el.audit.MaxIntDes;
import sysu.el.audit.MinIntDes;
import sysu.el.graph.undi.UndiGT;
import sysu.el.graph.undi.UndiGTAdjList;
import sysu.el.graph.undi.UndiGTAdjListVal;
import sysu.el.tuple.Tuple;
import sysu.el.tuple.Tuple.IIII;
import sysu.el.tuple.TupleInt;

//-EL-TODO: You should manager the TreeDiameter well.
public class TopoDiameter {
	public Max2IntDes<Integer> max2int;
	public Tuple.IIII[] nodesMax2; 
	public MaxInt maxDis = new MaxInt();
	
	public int center;
	public int diameter;
	
	public ArrQueueInt queue;
	public BoolArray isVisited;
	public int[] maxLen;
	public int[] fa;
	public UndiGTAdjList graph;

	public TopoDiameter(UndiGTAdjList g){
		graph = g;
		// Algor Temperorary Variables
		nodesMax2 = new Tuple.IIII[g.getNodeNum()];
		for (int i=0; i<g.getNodeNum(); ++i)
			nodesMax2[i] = new Tuple.IIII(0, 0, 0, 0);
		// Reset every time
		this.queue = new ArrQueueInt(graph.getNodeNum());
		this.isVisited = new BoolArray(g.getNodeNum());
		this.maxLen = new int[g.getNodeNum()];
		this.fa = new int[g.getNodeNum()];
		// Read-Only
		graph = g;
	}
	
	public void reset(){
		for (int i=0; i<graph.getNodeNum(); ++i){
			nodesMax2[i].reset(0);
			maxLen[i] = 1;
		}
		maxDis.reset();
		queue.reset();
		isVisited.reset();
		// MaxLen is left to step 1 to initialize
	}

	public int[] calTreeDiameter(int root){
		reset();
		
//-STEP: Stretch the graph into a tree with BFS		
		queue.add(root);
		isVisited.setVisited(root);
		while (queue.isEmpty()==false){
			int id = queue.forward();
			int nodes[] = graph.getList(id);
			for (int i=0; i<graph.getDegree(id); ++i){
				int node = nodes[i];
				if (isVisited.isVisited(node)) continue;
				queue.add(node);
				isVisited.setVisited(node);
				fa[node] = id;
			}
		}
		//System.out.println(Sig.mkString(queue.list, ",\t"));
		//System.out.println(Sig.mkString(fa, ",\t"));
//-STEP: Calculate the Longest Path in Tree
		int[] nodes = queue.elements();
		assert(nodes[0] == root);
		MaxIntDes<Integer> center = new MaxIntDes<Integer>(0);
		// Exclude i == 0
		for (int i=graph.getNodeNum()-1; i>0; --i){
			int cur_node = nodes[i];
			int fa_node = fa[cur_node];
			maxLen[fa_node] = Math.max(maxLen[fa_node], maxLen[cur_node]+1);
			nodesMax2[fa_node].max2(maxLen[cur_node], cur_node);
			IIII tmp = nodesMax2[cur_node];
			center.sample(tmp.a + tmp.c + 1, cur_node);
			maxDis.sample(tmp.a+1);
		}
		IIII tmp = nodesMax2[root];
		center.sampleLast(tmp.a+tmp.c+1, root);
		
		//System.out.println(center.getAns() + "\t" + center.getDes());
		
//-STEP: Generate the Path according to data collected.
		int[] path = new int[center.getAns()];
		IIII node = nodesMax2[center.getDes()];
		path[node.a] = center.getDes();
		int nextnode = node.b;
		for (int i=node.a-1; i>=0; --i){
			path[i] = nextnode;
			nextnode = nodesMax2[nextnode].b;
		}
		nextnode = node.d;
		for (int i=node.a+1; i<center.getAns(); ++i){
			path[i] = nextnode;
			nextnode = nodesMax2[nextnode].b;
		}
		
		return path;
	}
	
	
	
	public Tuple.TDbl<Integer, Integer> calGraphDiameter_brute(){
		int[][] paths = new int[graph.getNodeNum()][];
		MinIntDes<Integer> min = new MinIntDes<Integer>();
		for (int i=0; i<graph.getNodeNum(); ++i){
			paths[i] = calTreeDiameter(i);
			min.sample(maxDis.getAns(), i);
			System.out.println(maxDis.getAns() + "\tFFF\t" +i);
		}
		return new Tuple.TDbl<Integer, Integer>(min.getAns(), min.getDes());
	}
	
	//-EL-TODO: This is wrong.
	public Tuple.TDbl<Integer, Integer> calGraphDiameter(){
		int[][] paths = new int[graph.getNodeNum()][];
		
		MinIntDes<Integer> min = new MinIntDes<Integer>();
		int root = 0;
		paths[root] = calTreeDiameter(root);
		int best_len = (paths[root].length+1);
		int best_root = 0;
		int prev;
		do{
			prev = root;
			root = paths[root][0];
			paths[root] = calTreeDiameter(root);
			if (best_len > paths[root].length){
				best_len = paths[root].length;
				best_root = root;
			}else break;
		}while (true);
		return new Tuple.TDbl<Integer, Integer>(best_len/2, paths[root][paths[root].length/2]);
	}
	
	public static void main(String[] args) {
		UndiGTAdjList graph = new UndiGTAdjList(9);
		int data[] = new int[]{0, 1, 1, 2, 1, 3, 2, 5, 2, 6, 3, 6, 4, 8, 5, 7, 6, 8, 7, 8};
		for (int i=0; i<data.length >> 1; i++){
			graph.addEdge(data[i<<1], data[(i<<1)+1]);
		}
		
		TopoDiameter td = new TopoDiameter(graph);
		for (int i=0; i<3; i++){
			int[] path = td.calTreeDiameter(1);
			assert(path.length==6);
			assert(path[path.length/2] == 2);
			System.out.println(Sig.mkString(path, "\t"));
		}
		
		System.out.println(td.calGraphDiameter_brute());
		System.out.println(td.calGraphDiameter().a + "\t"+ td.calGraphDiameter().b);
	}
}
